#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
/**
 * 递归法
 * 思考1：如果我使用left == NULL || right == NULL return false;这样可以吗？
 * 			不可以，因为左右子树同时为空的时候是对称的，要返回true
 * 思考2：如果我不要加else ，都是if判断后return，这样可以吗？
 * 			
 */
class Test1{
public:
	bool compare(TreeNode* left,TreeNode* right){
		// 排除空的情况
		if(left == NULL && right != NULL){
			return false;
		}else if(left != NULL && right == NULL){
			return false;
		}else if(left == NULL && right == NULL){
			return true;
		}else if(left->val != right->val){
			return false;
		}
		bool outside = compare(left->left,right->right);
		bool inside = compare(left->right,right->left);
		return outside && inside;
	}
	bool isSymmetric(TreeNode* root) {
		if(root==NULL){
			return true;
		}
		return compare(root->left,root->right);
	}
};
/**
 * 使用队列，中心思想就是成对成对的放入就行，后续取出也是成对拿来比较。
 * 因此，将queue换成stack，然后只需要修改对应的放入容器的方法，其他的都不用动。
 */
class Test2{
public:
	bool isSymmetric(TreeNode* root) {
		if(root == NULL){
			return true;
		}
		queue<TreeNode*> que;
		que.push(root->left);
		que.push(root->right);
		while(!que.empty()){
			TreeNode* leftNode = que.front();que.pop();
			TreeNode* rightNode = que.front();que.pop();
			// 如果左右子树都为空则继续
			if(leftNode == NULL && right == NULL){
				continue;
			}
			if(leftNode == NULL || right == NULL || leftNode->val != rightNode -> val){
				return false;
			}
			// 到这里，说明左右子树相等，继续判断
			que.push(leftNode->left);
			que.push(rightNode->right);
			que.push(leftNode->right);
			que.push(rightNode->left);
		}
		return true;
	}
};
int main(){
	
	return 0;
}
